package demo1;

import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //买卖股票的最佳时机1
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(max,prices[i]-prices[i-1]);
            min = Math.min(min,prices[i]);
        }
        return max;
    }

    //矩阵中的蛇
    public int finalPositionOfSnake(int n, List<String> commands) {
        int i = 0;
        int j = 0;
        for (String each : commands){
            if(each.equals("UP")) i--;
            else if(each.equals("DOWN")) i++;
            else if(each.equals("LEFT")) j--;
            else j++;
        }
        return (i*n)+j;
    }

    //最长递增子序列
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int i = 1; i < n; i++) {
            int flag = 0;
            max = 1;
            for (int j = 0; j < i; j++) {
                if(nums[i]>nums[j]) {
                    max = Math.max(max,dp[j]);
                    flag = 1;
                }
            }
            if(flag==1) dp[i] = max+1;
        }
        for (int i = 0; i < n; i++) max = Math.max(max,dp[i]);
        return max;
    }

    //摆动序列
    public int wiggleMaxLength(int[] nums) {
        int ret = 0;
        int left = 0;int right = 0;
        for(int i = 0;i<nums.length-1;i++){
            right = nums[i+1]-nums[i];
            if(right==0) continue;
            if(right*left<=0) ret++;
            left = right;
        }
        return ret+1;
    }

    public int wiggleMaxLength1(int[] nums) {
        int i = 0;
        for (i = 0; i < nums.length-1; i++) {
            if(nums[i]!=nums[i+1]) break;
        }
        if(i==nums.length-1) return 1;
        int len = nums.length;
        if(len==1) return 1;
        int ret = 1;
        int left = i; int right = i+1;int flag = 0;
        if(nums[left]<nums[right]) flag = 0;
        else flag=1;

        while(right<len){
            if (flag == 0) {
                if(nums[right]<nums[left]){
                    ret++;
                    flag = 1;
                }
            }else {
                if(nums[right]>nums[left]){
                    ret++;
                    flag = 0;
                }
            }
            left++; right++;
        }
        return ret+1;
    }
}
